#ifndef LIST_DEF_H
#define LIST_DEF_H

/*
    模仿STL 实现双向链表 ：
    带头结点
    1. 头结点的prev指向尾结点 ， 尾结点next头结点
    2. 链表为空 头结点 的 next 和 prev 指向自身
*/
#include "allocator.hpp"
#include "iterator.hpp"

namespace TingSTL {

template <class T>
struct list_node_base; // 头结点，不带数据域
template <class T>
struct list_node;
template <typename T>
class list_iterator;
template <typename T, typename Alloc>
class list;

template <typename T>
struct list_node_base {
    using base_ptr = list_node_base<T> *;
    using node_ptr = list_node<T> *;

    base_ptr next;
    base_ptr prev;

    node_ptr cast_node_ptr() {
        return static_cast<node_ptr>(&*this);
    }

    void swap(list_node_base &other) {
        std::swap(next, other.next);
        std::swap(prev, other.prev);
    }

    inline void link_self() {
        next = this;
        prev = this;
    }
};

template <typename T>
struct list_node : public list_node_base<T> {
    T value;
};

template <typename T, typename Alloc = allocator<T>>
class list {
public:
    using allocator_type = typename Alloc;

    using value_type = typename allocator_type::value_type;
    using pointer = typename allocator_type::pointer;
    using const_pointer = typename allocator_type::const_pointer;
    using reference = typename allocator_type::reference;
    using const_reference = typename allocator_type::const_reference;
    using difference_type = typename allocator_type::difference_type;
    using size_type = typename allocator_type::size_type;

    using base_node = typename list_node_base<T>;
    using node = typename list_node<T>;
    using base_ptr = typename list_node_base<T>::base_ptr;
    using node_ptr = typename list_node<T>::node_ptr;
    using base_node_alloc =
        typename rebind_alloc_t<allocator_type, list_node_base<T>>;
    using node_alloc = typename rebind_alloc_t<allocator_type, list_node<T>>;

    using iterator = typename list_iterator<value_type>;
    using const_iterator = typename const list_iterator<value_type>;

private:
    base_node *_head_node;
    size_type _size;

public:
    // ///////////////////////////// 构造 析构  //////////////////////////

    list() {
        _head_node = base_node_alloc::allocate(1);
        _head_node->link_self();
        _size = 0;
    }

    ~list() {
        clear();
        base_node_alloc::deallocate(_head_node);
    }
    list(const list &other) {
        _head_node->link_self();
        _size = other._size;
        for (const auto &value : other) {
            auto node = createNode(value);
            linkAtBack(node);
        }
    }

    list(list &&other) {
        _size = other._size;
        _head_node->link_self();
        this->swap(other);
    }

    list &operator=(list other) {
        this->swap(other);
        return *this;
    }

    // //////////////////////////// 容量相关  ////////////////////////////

    inline size_type size() const noexcept {
        return _size;
    }

    inline bool empty() const noexcept {
        return _size == 0;
    }

    void clear() {
        auto curNode = _head_node->next;
        decltype(curNode) next{};
        while (curNode != _head_node) {
            next = curNode->next;
            destroyNode(curNode->cast_node_ptr());
            curNode = next;
        }
        _head_node->link_self();
        _size = 0;
    }
    // //////////////////////////// 迭代器相关  ////////////////////////////

    inline iterator begin() noexcept {
        return {_head_node->next};
    }

    inline iterator begin() const noexcept {
        return {_head_node->next};
    }

    inline iterator end() noexcept {
        return {_head_node};
    }

    inline iterator end() const noexcept {
        return {_head_node};
    }

    inline const_iterator cbegin() const noexcept {
        return {_head_node->next};
    }

    inline const_iterator cend() const noexcept {
        return {_head_node};
    }

    // ///////////////////////////// 访问容器， 插入 , 删除相关 ///////////////////////

    inline reference front() {
        TING_ASSERT(!empty(), "list is empty");
        return *begin();
    }

    inline reference back() {
        TING_ASSERT(!empty(), "list is empty");
        return *end();
    }

    // 插入元素 ， 返回插入位置
    template <typename... Args>
    iterator emplace(const_iterator &pos, Args &&...args) {
        TING_ASSERT(pos != nullptr, "list emplace pos error");
        auto node = createNode(std::forward<Args>(args)...);
        this->linkAtPos(pos._node, node);
        ++_size;
        return {node};
        return nullptr;
    }

    template <typename... Args>
    iterator emplace_front(Args &&...args) {
        auto node = createNode(std::forward<Args>(args)...);
        this->linkAtFront(node);
        ++_size;
        return {node};
        return nullptr;
    }

    template <typename... Args>
    iterator emplace_back(Args &&...args) {
        auto node = createNode(std::forward<Args>(args)...);
        this->linkAtBack(node);
        ++_size;
        return {node};
    }

    // 删除pos 位置的元素，返回删除位置的下一个位置
    iterator erase(const_iterator &pos) {
        TING_ASSERT(pos != nullptr && pos != cend(), "list erase pos error");
        base_ptr node = pos._node;
        base_ptr next = node->next;
        --_size;
        unlinkNode(node);
        destroyNode(node->cast_node_ptr());
        return {next};
    }

    void pop_back() {
        TING_ASSERT(!empty(), "list is empty,cant pop");
        --_size;
        auto node = _head_nod->prev;
        unlinkNode(node);
        destroyNode(node->cast_node_ptr());
    }

    void pop_front() {
        TING_ASSERT(!empty(), "list is empty,cant pop");
        --_size;
        auto node = _head_node->next;
        unlinkNode(node);
        destroyNode(node->cast_node_ptr());
    }

    // find 返回查找位置的迭代器 , 没有找到返回 end
    iterator find(const_reference target) {
        for (auto cur = _head_node->next; cur != _head_node;
             cur = cur->next) {
            if (cur->cast_node_ptr()->value == target) {
                return {cur};
            }
        }
        return {_head_node};
    }

    // //////////////////////////// 兼容作业 api //////////////////////////
    node_ptr push(const_reference v) {
        auto pos = emplace_back(v);
        return pos._node;
    }

    node_ptr insert(node_ptr pos, const_reference v) {
        iterator iter_pos(pos);
        return emplace(iter_pos, v)._node;
    }

    // 查找所在节点 ，没有查找到 返回 nullptr
    node_ptr findNode(const_reference v) {
        auto pos = find(v);
        return pos != end() ? pos._node : nullptr;
    }

    void removeNode(node_ptr pos) {
        iterator iter_pos(pos);
        erase(iter_pos);
    }

    void popAll() {
        clear();
    }
    // ///////////////////////////// misc ///////////////////////////////

    void swap(list &other) {
        std::swap(_size, other._size);
        std::swap(_head_node, other._head_node);
    }

private:
    // ///////////////////////////// 内存管理  //////////////////////////

    template <typename... Args>
    static node_ptr createNode(Args &&...args) {
        node_ptr ret = node_alloc::allocate(1);
        try {
            allocator_type::construct(&ret->value,
                                      std::forward<Args>(args)...);
        } catch (...) {
            node_alloc::deallocate(ret);
            throw;
        }
        return ret;
    }

    static void destroyNode(node_ptr p) {
        allocator_type::destroy(&p->value);
        node_alloc::deallocate(p);
    }

    // ///////////////////////////// 链表组织 相关算法
    // //////////////////////////

    // 将 link_node 连接到pos 处，fix: 需要特殊处理 插入first和last 用于保持环状
    void linkAtPos(base_ptr pos, base_ptr link_node) {
        if (pos == _head_node) // 插入队尾
        {
            linkAtBack(link_node);
            return;
        }

        if (pos == _head_node->next) {
            linkAtFront(link_node);
            return;
        }

        pos->prev->next = link_node;
        link_node->next = pos;
        link_node->prev = pos->prev;
        pos->prev = link_node;
    }

    void linkAtFront(base_ptr link_node) {
        link_node->prev = _head_node;
        link_node->next = _head_node->next;
        link_node->next->prev = link_node;
        _head_node->next = link_node;
    }

    void linkAtBack(base_ptr link_node) {
        link_node->next = _head_node;
        link_node->prev = _head_node->prev;
        link_node->prev->next = link_node;
        _head_node->prev = link_node;
    }

    // node 节点解开连接
    static void unlinkNode(base_ptr node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
};

template <typename T>
class list_iterator : public base_iterator<bidirectional_iterator_tag, T> {
    friend class list<T>;

public:
    using base_ptr = typename list_node_base<T>::base_ptr;
    using node_ptr = typename list_node<T>::node_ptr;

private:
    base_ptr _node; // 当前索引node
public:
    list_iterator() :
        base_iterator(nullptr) {
    }

    list_iterator(base_ptr p) :
        _node(p) {
    }

    list_iterator(const list_iterator &other) :
        _node(other._node) {
    }

    inline reference operator*() const {
        return _node->cast_node_ptr()->value;
    }

    inline pointer operator->() const {
        return &(_node->cast_node_ptr()->value);
    }

    // 双向迭代器 支持 ++ -- 迭代
    inline list_iterator &operator++() {
        _node = _node->next;
        return *this;
    }

    inline list_iterator operator++(int) {
        list_iterator temp{*this};
        _node = _node->next;
        return temp;
    }

    inline list_iterator &operator--() {
        _node = _node->prev;
        return *this;
    }

    inline list_iterator operator--(int) {
        list_iterator temp{*this};
        _node = _node->prev;
        return temp;
    }

    inline bool operator==(const list_iterator &other) const {
        return _node == other._node;
    }

    inline bool operator!=(const list_iterator &other) const {
        return _node != other._node;
    }
};
} // namespace TingSTL

namespace std {
template <typename T, typename Alloc>
void swap(TingSTL::list<T, Alloc> &lhs, TingSTL::list<T, Alloc> &rhs) {
    lhs.swap(rhs);
}
} // namespace std
#endif